# 自己的解法
import math
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.kmax = k
        nums.extend([-math.inf,math.inf])
        self.numslist = sorted(nums)
    def add(self, val: int) -> int:
        for i in range(len(self.numslist)):
            if val < self.numslist[i] and val >= self.numslist[i-1]:
                self.numslist.insert(i, val)
                break
        return self.numslist[-self.kmax-1]

# 使用内置模块heapq，但要注意heapq只是以堆的形式来维护list，本质还是list对象
# 使用所有的方法都是以参数的形式来传入list


import heapq
class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > self.k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        # 需要注意的是heapreplace这个函数直接是替代堆顶元素，然后再更新堆
        # heapq.heapreplace(self.heap, val)


        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        # 另外需要注意在使用heap【0】时，想一下是不是可以为空heap。
        elif self.heap[0] < val:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]


# 大佬的答案，
# class KthLargest(object):
#
#     def __init__(self, k, nums):
#         """
#         :type k: int
#         :type nums: List[int]
#         """
#         # self k
#         self.k = k
#         self.heap = nums
#         # heap其实就是个list
#         heapq.heapify(self.heap)
#         # 减小到k
#         while len(self.heap) > k:
#             heapq.heappop(self.heap)
#
#     def add(self, val):
#         """
#         :type val: int
#         :rtype: int
#         """
#         # 不过堆不够，则直接添加进去
#         if len(self.heap) < self.k:
#             heapq.heappush(self.heap, val)
#         elif self.heap[0] < val:
#             # 新的值更大，更新
#             heapq.heapreplace(self.heap, val)
#
#         return self.heap[0]

# 。作者：shuai-shuai-31
# 链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/solution/pythonde-heapqben-shen-jiu-shi-xiao-ding-dui-by-sh/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处